#include <iostream>
using namespace std;
#include <vector>
#include <climits>

//version 1
//直接拿位图了，
class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        vector<int> ret;
        int N = nums.size() + 2;
        //使用位图
        vector<int> bitmap(938, 0);
        for(auto x : nums) 
            bitmap[x / 32] |= (1 << (x % 32));
        for(int i = 1; i <= N; ++i){
            int ibit = (1 << (i % 32)) & bitmap[i / 32];
            if(!ibit) ret.push_back(i);
        }
        return ret;
    }
};



//version 2
//设未出现的数字a和b
//如果把nums + a + b 和 nums两个部分看成一个整体 -> 就转变为了“其他数字出现两次，找出出现1次的两个数”
//转化后的思路我们是知道的！
class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        vector<int> ret(2, 0);


        //为了方便操作，直接把两个部分都放到一个数组里面去
        int xor_num = 0, N = nums.size() + 2;
        for(int i = 1; i <= N; ++i) nums.push_back(i);
        
        //1.找到异或数字
        for(auto x : nums) xor_num ^= x;
        //2.找到lowbit
        int lowbit = xor_num == INT_MIN ? xor_num : xor_num & (-xor_num);
        //3.分区
        for(auto x : nums){
            if(x & lowbit) ret[1] ^= x;
            else ret[0] ^= x;
        }
        return ret;
    }
};

